package com.Sep_Two;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution637 {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res=new ArrayList<>();
        Deque<TreeNode> deque=new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty())
        {
            double levelSum=0.0;
            //TreeNode top=deque.peek();
            int levelSize=deque.size();
            for (int i=0;i<levelSize;i++)
            {
                TreeNode temp=deque.pollFirst();
                levelSum+=temp.val;
                if(temp.left!=null) deque.offer(temp.left);
                if (temp.right!=null) deque.offer(temp.right);
            }
            res.add(levelSum/levelSize);
        }
        return res;
    }


    static class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
